// 测试链接 : https://www.luogu.com.cn/problem/P1177

import java.io.*;

public class MergeSort {

    /*
    public static int MAX = 10001;
    public static int[] arr = new int[MAX];

    public static int[] help =new int[MAX];

    public static int n;

    public static void main1(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n = (int) in.nval; //获取数组的个数
        for (int i = 0; i < n; ++i) {
            in.nextToken();//向下走
            arr[i] = (int) in.nval;
        }
        //归并排序
        mergeSort(0,n-1);
        for(int i = 0 ; i < n-1; ++i) {
            out.println(arr[i] + " ");
        }
        out.println(arr[n-1]);
        out.flush();
        out.close();
        br.close();
    }
    */

    public static int[] arr = {1,6,8,3,5};
    public static int n = arr.length;
    public static int[] help = new int[n];

    public static void main(String[] args) {
        //mergeSort1(0,n-1);

        mergeSort2(n);
        for(int i = 0; i < n ; ++i) {
            System.out.print(arr[i] + " ");
        }
    }


    //归并排序递归版本
    public static void mergeSort1(int l,int r) {
        if(l == r) {
            return;
        }
        int m = l +( (r-l) >> 1 ); //(l+r)/2
        mergeSort1(l,m);
        mergeSort1(m+1,r);
        merge(l,m,r);
    }

    //归并排序非递归版本
    public static void mergeSort2(int n) { //n为数组的个数
        for(int step = 1; step < n; step <<= 1 ) { //步长依次是1，2，4，8...
            int l = 0; //每次从第一个点开始
            while (l < n) {
                int m = l + step-1;
                if(m+1 >= n) { //如果右部分没有数就等到下一组进行排序
                    break;
                }
                //右侧还有数
                int r = Math.min(m+step , n-1);
                merge(l,m,r);
                l = r + 1;
            }
        }
    }


    //归并，合并两个数组使有序
    public static void merge(int l,int m, int r) {
        int a = l;
        int b = m+1;
        int index = l;
        while ( a <= m && b <= r ) {
            help[index++] =arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while (a <= m) {
            help[index++] = arr[a++];
        }
        while (b <= r ) {
            help[index++] = arr[b++];
        }
        //将排序好的辅助数组填回原来的数组的对应区间
        index = l;
        while(index <= r) {
            arr[index] = help[index];
            index++;
        }
    }

}
